# 有多个层，每层有8个格子空间；
# 每层放置若干个物品，每个物品占用若干个格子空间；
# 物品不可以跨层放置；
# 物品不可以旋转，只能水平移动
# 每层物品之间有可能有间隔,也有可能没有间隔

class DropGame:
    GRID_WIDTH = 8  # 每层的格子数量
    GRID_HEIGHT = 10 # 最大层数

    def __init__(self):
        self.state = []  # 存储每层的物品信息
        self.next_layer = [] # 下一层的物品信息,还未添加到state中
        self.b_display_show = False

    def clone(self):
        new_game = DropGame()
        new_game.state = [layer.copy() for layer in self.state]
        new_game.next_layer = self.next_layer.copy()
        new_game.b_display_show = False
        return new_game

    # 设置下一层
    # input_str: 物品表达, ‘.’表示空格，‘#’表示物品,跟随的数字表示空格或物品占用的格子数量
    def set_next_layer(self, input_str):
        self.next_layer = []
        start = 0
        i = 0
        while i < len(input_str):
            if input_str[i] == '.':
                i += 1
                gap_str = ''
                while i < len(input_str) and input_str[i].isdigit():
                    gap_str += input_str[i]
                    i += 1
                gap = int(gap_str) if gap_str else 1
                start += gap
            elif input_str[i] == '#':
                i += 1
                size_str = ''
                while i < len(input_str) and input_str[i].isdigit():
                    size_str += input_str[i]
                    i += 1
                if size_str == '':
                    size = 1
                else:
                    size = int(size_str)
                self.next_layer.append((start, size))
                start += size
        if self.b_display_show:
            self.display('设置下一层')

    # 下一层加入到state中
    def commit_next_layer(self):
        if self.next_layer:
            self.add_layer(self.next_layer, b_display= False)
            self.next_layer = []
            if self.b_display_show:
                self.display('提交下一层')

    # 添加新层
    #items: 每层的物品信息，每个物品的位置和占用的格子数量
    #       用元组表示，(start, size)，0<=start<size<=8
    def add_layer(self, items, b_display= True):
        self.state.append(items)
        # 检查物品是否超出格子范围
        for start, size in items:
            if start + size > DropGame.GRID_WIDTH:
                raise ValueError("物品超出格子范围")
        # 检查物品是否重叠
        for i in range(len(items)):
            for j in range(i+1, len(items)):
                if items[i][0] < items[j][0] + items[j][1] and items[j][0] < items[i][0] + items[i][1]:
                    raise ValueError("物品重叠")
        if self.b_display_show and b_display:
            self.display('添加新层')

    # 添加新层
    # input_str: 每层的物品表达, ‘.’表示空格，‘#’表示物品,跟随的数字表示空格或物品占用的格子数量
    # 例如: ".2#2#1.2#1" 表示该层有3个物品，
    #    0，1格子为空，2-3格子为第一个物品（占2格），4格子为第二个物品（占1格），5-6格子为空，7格子为第三个物品（占1格）
    def add_layer_by_str(self, input_str: str):
        items = []
        start = 0
        i = 0
        while i < len(input_str):
            if input_str[i] == '.':
                i += 1
                gap_str = ''
                while i < len(input_str) and input_str[i].isdigit():
                    gap_str += input_str[i]
                    i += 1
                gap = int(gap_str) if gap_str else 1
                start += gap
            elif input_str[i] == '#':
                i += 1
                size_str = ''
                while i < len(input_str) and input_str[i].isdigit():
                    size_str += input_str[i]
                    i += 1
                if size_str == '':
                    size = 1
                else:
                    size = int(size_str)
                items.append((start, size))
                start += size
            else:
                raise ValueError("无效的输入字符")
        self.add_layer(items)
    # 添加新层
    # numbers: 每层的物品依次表达, 占用格子数量，和间隔长度交替出现
    def add_layer_by_gap(self, numbers: list[int]):
        items = []
        start = 0
        for i in range(0, len(numbers), 2):
            size = numbers[i]
            gap = numbers[i+1]
            items.append((start, size))
            start += size + gap
        self.add_layer(items)

    # 跌落操作:某一层的物品下方如果没有物品，则该物品下落一层；从上到下依次检查每一层的物品是否可以下落
    # 返回是否有物品下落
    def drop(self):
        has_drop = False
        # 从倒数第二层往上遍历
        for i in range(len(self.state) - 2, -1, -1):
            upper_layer = self.state[i]
            lower_layer = self.state[i + 1]
            # 构建下层的占用格子表
            occupied = [False] * DropGame.GRID_WIDTH
            for start, size in lower_layer:
                for k in range(start, start + size):
                    occupied[k] = True
            new_upper_layer = []
            moved = [False] * len(upper_layer)
            for idx, (start, size) in enumerate(upper_layer):
                can_drop = True
                for k in range(start, start + size):
                    if k >= DropGame.GRID_WIDTH or occupied[k]:
                        can_drop = False
                        break
                if can_drop:
                    # 下落到下一层
                    lower_layer.append((start, size))
                    has_drop = True
                    moved[idx] = True
                    # 标记下层新占用
                    for k in range(start, start + size):
                        occupied[k] = True
                else:
                    new_upper_layer.append((start, size))
            # 更新上层，移除已下落的物品
            self.state[i] = new_upper_layer
        # 移除空层
        self.state = [layer for layer in self.state if layer]
        return has_drop
    
    def drop_all(self):
        has_drop = False
        index = 0
        while self.drop():
            index += 1
            has_drop = True
            if self.b_display_show:
                self.display(f'跌落{index}')
        return has_drop
    
    # 消层: 检查所有的层，是否有层被完全占满（即8个格子都被物品占用），如果有则消除该层
    # 返回是否有层被消除
    def clear_full_layer(self):
        has_clear = False
        i = 0
        while i < len(self.state):
            occupied = [False] * DropGame.GRID_WIDTH
            for start, size in self.state[i]:
                for k in range(start, start + size):
                    occupied[k] = True
            if all(occupied):
                self.state.pop(i)
                has_clear = True
                if self.b_display_show:
                    self.display('消层')
                # 不递增i，继续检查当前位置（因为pop后后面的层前移）
            else:
                i += 1
        return has_clear
    
    # 连跌带消
    def drop_and_clear(self):
        has_clear = False
        while self.drop_all():
            if self.clear_full_layer():
                has_clear = True
        return has_clear
    
    # 平移操作:将某个物品向左或向右平移若干格子，平移过程中不能与其他物品重叠，且不能超出格子范围
    # layer_index: 物品所在的层索引
    # item_index: 物品在层中的索引
    # distance: 平移距离（正数表示向右平移，负数表示向左平移）
    # 返回平移结果: 是否平移成功
    def shift_item(self, layer_index, item_index, distance):
        # 检查层索引是否合法
        if layer_index < 0 or layer_index >= len(self.state):
            errorinfo = f'层索引无效:物品{layer_index}层{item_index}'
            raise ValueError(errorinfo)
        # 检查物品索引是否合法
        layer = self.state[layer_index]
        if item_index < 0 or item_index >= len(layer):
            errorinfo = f'物品索引无效:物品{layer_index}层{item_index}'
            raise ValueError(errorinfo)
        layer = self.state[layer_index]
        item = layer[item_index]
        start, size = item
        # 计算新的位置
        new_start = start + distance
        # 检查新位置是否合法
        if new_start < 0 or new_start + size > DropGame.GRID_WIDTH:
            raise ValueError("平移超出格子范围")
        # 检查新位置是否与其他物品重叠
        for i in range(len(layer)):
            if i != item_index:
                other_start, other_size = layer[i]
                if new_start < other_start + other_size and other_start < new_start + size:
                    errorinfo = f'平移与其他物品重叠: 物品{layer_index}层{item_index}与物品{layer_index}层{i}重叠'
                    raise ValueError(errorinfo)
        # 平移物品
        layer[item_index] = (new_start, size)
        if self.b_display_show:
            self.display(f'移动{layer_index}层{item_index}物品{distance}格')

    #分数评价
    # 评价函数: 评价当前状态的分数
    # 分数计算规则:
    # 一共10个绝对层，从上往下绝对层从0到9;
    # 每层最大分数100. state的index为相对层，最后一个相对层作为绝对层9
    # 当层没有物品，那么满分100
    # 一个物品格的基础分数为5,一个物品的分数为: 物品长度*物品格的基础分数 + 物品长度的平方/2
    # 一层的分数为: 100 - 所有物品的分数累计 * 层系数
    # 绝对层的层系数从9到0,依次递增0.05分别如下：1.00,1.05,1.10,...,1.45
    # state分数 = 所有层的分数总和
    # 返回评价分数
    def score(self):
        score = 0
        for absolute_layer_index in range(DropGame.GRID_HEIGHT):
            layer_score = 0
            x = 1.00 + 0.05 * (DropGame.GRID_HEIGHT - absolute_layer_index - 1) #系数
            empty_count = DropGame.GRID_HEIGHT - len(self.state)
            if absolute_layer_index < empty_count: #如果是空层
                layer_score = 100
            else:
                logic_layer_index = DropGame.GRID_HEIGHT - absolute_layer_index - 1
                layer = self.state[logic_layer_index]
                s = 0
                for idx, (start, size) in enumerate(layer):
                    s += size * 5 + size * size / 2
                layer_score = 100 - s * x

            score += layer_score
        return score

    def _display_layer(self, layer):
        # ANSI颜色码，8种颜色
        colors = [
            '\033[91m',  # 红
            '\033[92m',  # 绿
            '\033[93m',  # 黄
            '\033[94m',  # 蓝
            '\033[95m',  # 紫
            '\033[96m',  # 青
            '\033[90m',  # 灰
            '\033[97m',  # 白
        ]
        reset = '\033[0m'
        grid = ['.'] * DropGame.GRID_WIDTH
        color_grid = [''] * DropGame.GRID_WIDTH
        for idx, (start, size) in enumerate(layer):
            color = colors[idx % len(colors)]
            for i in range(start, start + size):
                grid[i] = '#'
                color_grid[i] = color
        # 输出带颜色的格子
        line = ''
        for i in range(DropGame.GRID_WIDTH):
            if grid[i] == '#':
                line += f"{color_grid[i]}#{reset}"
            else:
                line += '.'
        print(line)
    def display(self, extinfo):
        for layer in self.state:
            self._display_layer(layer)
        # 打印一条横线
        print('-' * DropGame.GRID_WIDTH)
        # 输出下一层
        self._display_layer(self.next_layer)
        print(f'信息: {extinfo}')
        print(f'分数: {self.score()}')
        print()
    
    #获取平移列表
    def getMoveList(self):
        move_list = [] #格式: (layer_index, item_index, +-移动距离)
        for layer_index, layer in enumerate(self.state):
            gap_counts = []
            # 获取每层物品之间的空隙，一共物品数+1个空隙
            for item_index, (start, size) in enumerate(layer):
                if item_index == 0:
                    gap_counts.append(start)  # 第一个物品前的空隙
                else:
                    prev_start, prev_size = layer[item_index - 1]
                    gap_counts.append(start - (prev_start + prev_size))  # 物品之间的空隙
            gap_counts.append(DropGame.GRID_WIDTH - (layer[-1][0] + layer[-1][1]))  # 最后一个物品后的空隙
            for item_index, (start, size) in enumerate(layer):
                gap = gap_counts[item_index]
                for i in range(gap):
                    move_list.append((layer_index, item_index, -i-1))
                gap = gap_counts[item_index + 1]
                for i in range(gap):
                    move_list.append((layer_index, item_index, i+1))
                     
        return move_list

def solve(game: DropGame):
    print("求解中...")
    # 这里可以添加求解逻辑，目前只是简单地显示当前状态
    move_list = game.getMoveList()
    print(f"当前可移动物品列表: {move_list}")
    for move in move_list:
        has_clear = False
        next_game = game.clone()
        next_game.shift_item(move[0], move[1], move[2])
        if next_game.drop_and_clear():
            has_clear = True
        next_game.commit_next_layer()
        if next_game.drop_and_clear():
            has_clear = True
        if has_clear:
            next_game.display(f'求解: 移动{move}有消除')
    game.display('原始状态')

# 测试用例
game = DropGame()
game.b_display_show = True
# game.add_layer([(0, 2), (3, 1), (6, 2)])
# game.add_layer([(1, 1), (4, 2), (7, 1)])
# game.add_layer([(2, 3), (5, 1)])
# game.display()
# game.add_layer([(0, 3), (4, 2)])  # 添加新层
# game.display()
# game.add_layer([(1, 2), (4, 3)])  # 添加新层
# game.display()
# game.add_layer_by_gap([2, 1, 3, 1, 1, 0])
# game.display()
# game.add_layer_by_str("###..#")
# game.display()

#实现交互式输出，用户输入#.符号表示一层物品，输入exit退出
# 每次输入后显示当前所有层的物品情况
while True:
    print("1. move 层索引 移动距离(左-x/右x)")
    print("2. add 新层的#.符号表示")
    print("3. set 设置下一层的#.符号表示")
    print("4. solution 求解")
    print("5. exit 退出")
    layer_str = input("请输入操作:")
    if layer_str == "exit":
        break
    try:
        if layer_str.startswith("move"):
            parts = layer_str.split()
            if len(parts) < 4:
                print("无效的移动命令格式")
                continue
            layer_index = int(parts[1])
            item_index = int(parts[2])
            distance = int(parts[3])
            game.shift_item(layer_index, item_index, distance)
            game.drop_and_clear()
            game.commit_next_layer()
            game.drop_and_clear()
            continue
        if layer_str.startswith("add"):
            parts = layer_str.split()
            if len(parts) != 2:
                print("无效的添加命令格式")
                continue
            layer_str = parts[1]
            game.add_layer_by_str(layer_str)
            game.drop_and_clear()
            continue
        if layer_str.startswith("set"):
            parts = layer_str.split()
            if len(parts) != 2:
                print("无效的设置命令格式")
                continue
            layer_str = parts[1]
            game.set_next_layer(layer_str)
            continue
        if layer_str.startswith("solution"):
            solve(game)
            continue
        if layer_str.startswith("exit"):
            break
    except ValueError as e:
        print(e)